package LeetCode75;

/**
 * 1071. 字符串的最大公因子
 * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
 *
 * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：str1 = "ABCABC", str2 = "ABC"
 * 输出："ABC"
 * 示例 2：
 *
 * 输入：str1 = "ABABAB", str2 = "ABAB"
 * 输出："AB"
 * 示例 3：
 *
 * 输入：str1 = "LEET", str2 = "CODE"
 * 输出：""
 *
 *
 * 提示：
 *
 * 1 <= str1.length, str2.length <= 1000
 * str1 和 str2 由大写英文字母组成
 */
public class T1071_字符串的最大公因子 {

    //使用 递归判断是否可以整除
    //方法二 如果str1+str2 == str2+str1
    public static String gcdOfStrings(String str1, String str2) {

        int minLength = Math.min(str1.length(), str2.length());
        String str = str1.length() > str2.length() ? str1 : str2;
        String subString = str1.length() > str2.length() ? str2 : str1;

        for (int i = minLength; i > 0; i--) {
            if (check(str, subString.substring(0, i)) && check(subString, subString.substring(0, i))) {
                return subString.substring(0, i);
            }
        }

        return "";


    }

    //检查是否可以整除
    public static boolean check(String str, String subString) {

        //判断是否是以subString 开头 如果是 就截掉 进入下一层递归 ,如果不是就返回false
        if (str.length() == 0) {
            return true;
        }
        if (str.length() % subString.length() == 0 && str.startsWith(subString)) {
            return check(str.substring(subString.length()), subString);
        } else {
            return false;
        }
    }


    //辗转相处法
    //为什么 不需要判断a b 的大小? 在gcd(b,a%b)这段代码中 如果b>a 如b=6,a=4  就会出现入参后就变成了 gcd(6,4)
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        if (a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        String s = gcdOfStrings("TAUXXTAUXXTAUXXTAUXXTAUXX", "TAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXXTAUXX");
        int gcd = gcd(4, 6);
        System.out.println(gcd);
    }

}
